Service chains define a set of services or service functions (e.g., firewalls, Deep Packet Inspection, Layer 2 forwarding service, Layer 3 forwarding service, etc.), and their order (service1→service2) to be applied to selective packets as they are forwarded through a network. This is also referred to as service function chaining (SFC) and has been widely deployed by institutions, such as government agencies, organizations, companies. The security departments of such institutions may require a proof that packets of a certain application are processed in accordance with an institution's security policy. For example, if a packet flow is supposed to go through a series of service functions, a proof that all packets of the flow actually go through the service chain specified by the institution's policy is required. In case the packets of a flow are not properly processed, a network device, such as a domain edge device, would be required to identify the policy violation and take corresponding actions (e.g. drop or redirect the packet, send an alert etc.) corresponding to the institution's policy.